package com.yjz.leetcode.二叉树学习.二三四树;

import java.util.Objects;

import static java.util.Objects.isNull;
import static java.util.Objects.nonNull;

/**
 * @author :yuanJinZhong
 * @description: 2-3-4 树节点类,  234 树:每个节点做多是3个数据项，最多有四个子节点，2-3-4 代表子节点树
 * 1个数据项的节点有2个子节点
 * 2个数据项的节点有3个子节点
 * 3个数据项的节点有4个子节点
 * 子节点数+1=当前节点数据项数
 * 234树是二叉搜索的变种，所以也是左子节点所有数据项小于父节点，右子节点所有数据项大于父节点
 * （数据项里的每一个值看成一个节点，结合图来看比较好理解）
 * @date :2018/12/2-10:26
 */
public class Node {

  public static final int ORDER = 4;

  /**
   * 表示该节点有多少数据项
   */
  private int numItems;

  /**
   * 父节点
   */
  private Node parent;

  /**
   * 存储子节点的数组,最多有4个子节点
   */
  private Node childArry[] = new Node[ORDER];

  /**
   * 存储节点数据项的数组,一个节点最多有3个数据项
   */
  private DataItem itemArry[] = new DataItem[ORDER - 1];

  /**
   * 链接子节点
   *
   * @param childIndex 第几个子节点
   * @param child      子节点实体
   */
  public void connectChild(int childIndex, Node child) {
    childArry[childIndex] = child;
    if (Objects.nonNull(child)) {
      child.parent = this;
    }
  }

  /**
   * 断开有指定下表的子节点的链接，并返回该子节点
   *
   * @param childIndex
   * @return
   */
  public Node disConnectChild(int childIndex) {
    Node tempNode = childArry[childIndex];
    childArry[childIndex] = null;
    return tempNode;
  }

  /**
   * 得到节点的指定下标的子节点
   *
   * @param childIndex
   * @return
   */
  public Node getChild(int childIndex) {
    return childArry[childIndex];
  }

  /**
   * 得到父节点
   *
   * @return
   */
  public Node getParent() {
    return parent;
  }

  /**
   * 判定当前节点是否是叶子节点
   *
   * @return
   */
  public boolean isLeaf() {
    return isNull(childArry[0]) ? true : false;
  }

  /**
   * 得到当前节点的数据项的个数
   *
   * @return
   */
  public int getNumItems() {
    return numItems;
  }

  /**
   * 得到当前节点指定下标数据项
   *
   * @param itemIndex
   * @return
   */
  public DataItem getItem(int itemIndex) {
    return itemArry[itemIndex];
  }

  /**
   * 判断当前节点的数据项是否满了(max is 3)
   *
   * @return
   */
  public boolean isDataItemFull() {
    return numItems == ORDER - 1 ? true : false;
  }

  /**
   * 查找数据项在节点中的下标
   *
   * @param key 实现{@link Comparable}接口的数据项
   * @return
   */
  public int findItem(Comparable key) {
    for (int j = 0; j < ORDER - 1; j++) {
      if (itemArry[j] == null) {
        break;
      } else if (itemArry[j].getData().compareTo(key) == 0) {
        return j;
      }
    }
    return -1;
  }

  /**
   * 将数据项插入到节点,并返回节点下标
   *
   * @param newDataItem 数据项 值对象(V O)
   * @return
   */
  public int insertItem(DataItem newDataItem) {
    numItems++;
    Comparable newDataValue = newDataItem.getData();
    //从后往前循环
    for (int j = ORDER - 2; j >= 0; j--) {
      if (itemArry[j] == null) {
        continue;
      } else {
        Comparable itsData = itemArry[j].getData();
        //如果当前值比新值大则当前值向后移一位
        if (itsData.compareTo(newDataValue) > 0) {
          itemArry[j + 1] = itemArry[j];
        } else {
          //如果当前值比新值小,则将新值插入后一位
          itemArry[j + 1] = newDataItem;
          return j + 1;
        }
      }
    }
    //如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置
    itemArry[0] = newDataItem;
    return 0;
  }

  /**
   * 移除当前节点的最后一个数据项
   *
   * @return
   */
  public DataItem removeItem() {
    DataItem temp = itemArry[numItems - 1];
    itemArry[numItems - 1] = null;
    numItems--;
    return temp;
  }

  /**
   * 打印当前节点的所有数据项
   */
  public void disPlayNodeData() {
    for (DataItem dataItem : itemArry) {
      if (nonNull(dataItem)) {
        dataItem.display();
      }
    }
  }

}
